package cn.arnold.sort;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] array = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] temp = new int[array.length];
        sort(array, 0, array.length - 1, temp);
        System.out.println(Arrays.toString(array));
    }

    public static void sort(int[] array, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 向左递归分解
            sort(array, left, mid, temp);
            // 向右递归分解
            sort(array, mid + 1, right, temp);
            // 合并有序序列
            merge(array, left, right, mid, temp);
        }


    }

    /**
     * 合并的方法
     * @param array 待合并数组
     * @param left  左边有序序列的初始索引
     * @param right 右边有序序列的初始索引
     * @param mid   左边和右边的中间索引
     * @param temp  中转数组
     */
    public static void merge(int[] array, int left, int right, int mid, int[] temp) {
        int i = left;       // 第一组的起点i
        int j = mid + 1;    // 第二组的起点j，mid=(left+right)/2
        int t = 0;          // 中转数组的索引t
        // (一)、把左右两边的有序序列按照规则填充到temp数组
        // 直到左右两边的序列有一个序列处理完毕
        while (i <= mid && j <= right) {
            // 如果左边元素小于对应右边元素，则将左边元素填充到temp数组
            if (array[i] <= array[j]) {
                temp[t] = array[i];
                t++;
                i++;
            } else {
                temp[t] = array[j];
                t++;
                j++;
            }
        }
        // (二)、把有剩余序列的剩余元素依次填充到temp数组
        // 左边有剩余
        while (i <= mid) {
            temp[t] = array[i];
            t++;
            i++;
        }
        // 右边有剩余
        while (j <= right) {
            temp[t] = array[j];
            t++;
            j++;
        }
        // (三)、把temp数组拷贝到array（并不是每次都拷贝所有）
        for (i = 0; i < t; i++) {// 将排好序的数填回到array数组的对应位置
            array[left + i] = temp[i];
        }

    }
}
